package com.zxy.leetcode._00000_00099._00010_00019;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 *
 * 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 标签：回溯算法
 */
public class Test00017 {

    public static void main(String[] args) {
        Test00017 test = new Test00017();
        System.out.println(test.letterCombinations("23"));
    }

    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return list;
        }

        int len = digits.length();

        char[][] allDigits = {
                {'a', 'b', 'c'},
                {'d', 'e', 'f'},
                {'g', 'h', 'i'},
                {'j', 'k', 'l'},
                {'m', 'n', 'o'},
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'},
                {'w', 'x', 'y', 'z'}
        };

        backtrack(list, 0, len, new StringBuilder(), digits, allDigits);

        return list;
    }

    private void backtrack(List<String> result, int index, int len, StringBuilder selectStr, String digits, char[][] allDigits) {
        if (selectStr.length() == len) {
            result.add(selectStr.toString());
            return;
        }

        int num = digits.charAt(index) - '2';   // 下标从0开始，拼音键盘从'2'开始
        for (int i=0; i<allDigits[num].length; i++) {
            selectStr.append(allDigits[num][i]);
            backtrack(result, index + 1, len, selectStr, digits, allDigits);
            selectStr.deleteCharAt(selectStr.length() - 1);
        }

    }
}
